package leetcode;

import java.util.Arrays;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * @author niann
 * @description 两数之和 II - 输入有序数组  https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/
 * @since 2024/10/27 16:43
 **/
public class LeetCode167 {

    public static void main(String[] args) {
        var numbers = new int[]{1, 3, 4};
//        var numbers = new int[]{2, 7, 11, 15};
        Solution solution = new LeetCode167().new Solution();
        int[] ints = solution.twoSum(numbers, 5);
        System.out.println(Arrays.toString(ints));
    }

    public class Solution {


        /**
         * 超过时间限制
         *
         * @param numbers
         * @param target
         * @return
         */
        public int[] twoSumTest(int[] numbers, int target) {
            if (numbers.length == 0) {
                return new int[]{1, 2};
            }
            for (int i = 0; i < numbers.length; i++) {
                for (int j = i + 1; j < numbers.length; j++) {
                    if (numbers[i] + numbers[j] == target) {
                        return new int[]{i + 1, j + 1};
                    }
                }
            }
            return null;
        }

        /**
         * 双指针
         *
         * @param numbers
         * @param target
         * @return
         */
        public int[] twoSum(int[] numbers, int target) {
            if (numbers.length == 2) {
                return new int[]{1, 2};
            }
            if (numbers.length % 2 == 0) {
                for (int i = numbers.length / 2 - 1, lasti = i + 1; i >= 0; i--, lasti++) {
                    for (int j = i - 1, lastj = lasti + 1; j >= 0; j--, lastj++) {
                        if (numbers[i] + numbers[j] == target) {
                            return new int[]{j + 1, i + 1};
                        }
                        if (numbers[i] + numbers[lasti] == target) {
                            return new int[]{i + 1, lasti + 1,};
                        }
                        if (numbers[j] + numbers[lasti] == target) {
                            return new int[]{j + 1, lasti + 1};
                        }
                        if (numbers[i] + numbers[lastj] == target) {
                            return new int[]{i + 1, lastj + 1};
                        }
                        if (numbers[lasti] + numbers[lastj] == target) {
                            return new int[]{lasti + 1, lastj + 1};
                        }
                    }
                }
            } else {
                for (int i = numbers.length / 2, lasti = i + 1; i >= 0; i--, lasti++) {
                    for (int j = i - 1, lastj = lasti; j >= 0; j--, lastj++) {
                        if (numbers[i] + numbers[j] == target) {
                            return new int[]{j + 1, i + 1};
                        }
                        if (numbers[i] + numbers[lasti] == target) {
                            return new int[]{i + 1, lasti + 1};
                        }
                        if (numbers[j] + numbers[lasti] == target) {
                            return new int[]{j + 1, lasti + 1};
                        }
                        if (numbers[i] + numbers[lastj] == target) {
                            return new int[]{i + 1, lastj + 1};
                        }
                        if (numbers[lasti] + numbers[lastj] == target) {
                            return new int[]{lasti - 1, lastj + 1};
                        }
                    }
                }
            }
            return null;
        }
//        -------------------
    }

}


